#pragma once

#include <ttg/services.h>
#include <ttg/pipeline.h>
#include "CommonDefs.h"
#include <map>
#include <algorithm>

using std::map;
using namespace ttg;
using namespace ttg::services;
using namespace ttg::pipeline;


struct SplittedData {
	const Points *points;
	Points *res;
	size_t lowInd;
	size_t highInd;
	SplittedData(const Points *p1, Points *r, size_t l, size_t h): points(p1), res(r), lowInd(l), highInd(h) {}
};

class ttgSplitter :public Node<pair<const Points *, Points *>, SplittedData>
{
	private:
	protected:
		virtual void process(pair<const Points *, Points *> data)
		{
			size_t parts = services::CPUAnalyzer::getRef()->getCoreCount();
			size_t partSize = data.first->size() / parts;
			for (size_t i = 0; i < parts - 1; i++)
				sendNext(SplittedData(data.first, data.second, i * partSize, (i + 1) * partSize));
			sendNext(SplittedData(data.first, data.second, (parts - 1) * partSize, data.first->size()));
		}
	public:
};

struct MinMax {
	const Points *points;
	Points *res;
	Point mi, ma;
	MinMax(const Points *p1, Points *r, Point l, Point h): points(p1), res(r), mi(l), ma(h) {}
};

class ttgMiniMaxi: public Node<SplittedData, MinMax> {
protected:
	virtual void process(SplittedData data) {
		const Points &points = *data.points;
		Point mi = points[0];
		Point ma = mi;
		for (size_t i = data.lowInd; i < data.highInd; i++)
			if (mi.x > points[i].x)
				mi = points[i];
			else if (ma.x < points[i].x) 
				ma = points[i];
		sendNext(MinMax(data.points, data.res, mi, ma));
	}
};

struct BoundedSegment {
	const Points *points;
	Points *res;
	Point p1, p2;
	double n1, n2;
	BoundedSegment(const Points *p, Points *r, Point p11, Point p21, double k1, double k2):points(p),res(r),p1(p11),p2(p21),n1(k1),n2(k2) {}
};

class ttgMiniMaxiGather: public Node<MinMax, BoundedSegment> {
private:
	Point mi, ma;
	const Points *points;
	Points *res;
	bool first;
protected:
	virtual void process(MinMax data) {
		if (first) {
			first = false;
			points = data.points;
			res = data.res;
			mi = data.mi;
			ma = data.ma;
		} else {
			if (mi.x > data.mi.x)
				mi = data.mi;
			if (ma.x < data.ma.x)
				ma = data.ma;
		}
	}
	virtual void onEnd() {
		sendNext(BoundedSegment(points, res, ma, mi, 0, 1e100));
		sendNext(BoundedSegment(points, res, mi, ma, 1e100, 2e100));
	}
public:
	ttgMiniMaxiGather(): Node("ttgMiniMaxiGather", true), first(true) {}
};

struct HullPoint {
	Points *res;
	Point p;
	double key;
	HullPoint(Points *r, Point p1, double k):res(r),p(p1),key(k) {}
};

class ttgDivideConquer: public Node<BoundedSegment, HullPoint> {
protected:
	virtual void process(BoundedSegment data) {
		const Points &P = *data.points;
		double midN = (data.n1+data.n2)/2;
	    if (P.size() < 2) {
			sendNext(HullPoint(data.res, data.p1, data.n1));
			if (P.size())
				sendNext(HullPoint(data.res, P[0], midN));
	    } else {
			Points *P_reduced = new Points();
	        Points H1, H2;
		    Point p_far;

			p_far = divide(P, *P_reduced, data.p1, data.p2);

			sendThis(BoundedSegment(P_reduced, data.res, data.p1, p_far, data.n1, midN));
			//divide_and_conquer(P_reduced, H1, p1, p_far);
			sendThis(BoundedSegment(P_reduced, data.res, p_far, data.p2, midN, data.n2));
			//divide_and_conquer(P_reduced, H2, p_far, p2);
		}
	}
	long getDifficulty(BoundedSegment data) {
		if (data.points->size() < (1ULL << 31))
			return (long)data.points->size();
		else
			return (1LL << 31) - 1;
	}
};

class ttgFinalGather: public Node<HullPoint, Points *> {
private:
	std::map<double, Point> m;
	Points *res;
protected:
	virtual void process(HullPoint data) {
		res = data.res;
		m[data.key] = data.p;
	}
	virtual void onEnd() {
		res->resize(m.size());
		int i = 0;
		for (map<double, Point>::const_iterator it = m.begin(); it != m.end(); it++)
			(*res)[i++] = it->second;
		sendNext(res);
	}
	long getDifficulty(HullPoint data) {
		static long hack = 1;
		hack += 1;
		return hack;
	}
public:
	ttgFinalGather():Node("ttgFinalGather", true) {}
};

double ttgConvexHull(const Points &points, Points &res)
{
	Pipeline<pair<const Points *, Points *>, Points *> pl(wrap(new ttgSplitter()) + wrap(new ttgMiniMaxi()) + wrap(new ttgMiniMaxiGather()) + wrap(new ttgDivideConquer()) + wrap(new ttgFinalGather()));
	double t_start = ServiceBase::_Timer().getSeconds();
	pl.run(make_pair(&points, &res));
	double t_end = ServiceBase::_Timer().getSeconds();
	return t_end - t_start;
}
